
'''
@author: Kevin Zhao
@data:Nov 22,2012 
@note: 
insertion sort
merge sort
binary search recursive and iterative versions
'''
import math
def partial_insertion_sort(array,p,r):
    for j in range(p, r):
        i = j - 1
        key = array[j]#the item to be sorted currently
        while array[i] > key and i >= p:
            temp = array[i]
            array[i] = key
            array[i + 1] = temp
            i = i - 1
    return array
def insertion_sort(array):
    for j in range(1, len(array)):
        i = j - 1
        key = array[j]#the item to be sorted currently
        while array[i] > key and i >= 0:
            temp = array[i]
            array[i] = key
            array[i + 1] = temp
            i = i - 1
    return array
def merge(L_array, R_array):
    result = []
    i = 0
    j = 0
    #compare items from L_array and R_array and put the smaller one into the result array
    while i < len(L_array) and j < len(R_array) :
        if L_array[i] < R_array[j]:
            result.append(L_array[i])
            i = i + 1
        else:
            result.append(R_array[j])
            j = j + 1
    
    #when one of the two arrays runs out of items,we have to merge the rest of the another array's item to the result array
    if i >= len(L_array):
        result = result + R_array[j:]
    else:
        result = result + L_array[i:]
    return result


def merge_sort(array):
    mid_index = int(math.floor(len(array) / 2))
    #Sort step
    if len(array) <= 1:
        return array
    if len(array) == 2:
        if array[0] > array[1]:
            temp = array[0]
            array[0] = array[1]
            array[1] = temp
        return array
    #Split Step
    L_array = merge_sort(array[0:mid_index])
    R_array = merge_sort(array[mid_index :len(array)])
    #Merge Step
    result = merge(L_array, R_array)
    
    return result
'''
Binary Search Recursive Version
'''
def BSR(array,key):
    if len(array) == 0:
        return False
    mid = int(math.floor(len(array)/2))
    if key < array[mid]:
        return BSR(array[:mid],key)
    if key > array[mid]:
        return BSR(array[mid+1:],key)
    if key == array[mid]:
        return True   
'''
Binary Search Iterative Version
'''
def BSI(array,key):
    
    start_index = 0
    end_index = len(array)-1
    while start_index != end_index:
        mid = int(math.floor((start_index + end_index)/2))
        if key < array[mid]:
            end_index = mid
        if key > array[mid]:
            start_index = mid + 1
        if key == array[mid]:
            return True
    
    return False
        
      
#print insertion_sort([8,7,6,4,4,8,5,1,6,3,2,5,8,1,9,4])
#print merge_sort([8, 7, 6, 4, 4, 8, 5, 1, 6, 3, 2, 5, 8, 1, 9, 4])
#print BSR(merge_sort([8, 7, 6, 4, 4, 8, 5, 1, 6, 3, 2, 5, 8, 1, 9, 4]),4)
#print BSR(merge_sort([8, 7, 6, 4, 4, 8, 5, 1, 6, 3, 2, 5, 8, 1, 9, 4]),11)
#print BSI(merge_sort([8, 7, 6, 4, 4, 8, 5, 1, 6, 3, 2, 5, 8, 1, 9, 4]),4)
#print BSI(merge_sort([8, 7, 6, 4, 4, 8, 5, 1, 6, 3, 2, 5, 8, 1, 9, 4]),11)
